Cookies [and similar technologies] are ever present in the modern web.

They allow websites to track both the websites that we visit and how we engage with websites.

… but what about all those cookie popups?!

Source: Kretschmer et al 2021¹

I’m a 26-year-old British Asian woman, working in media and living in an SW postcode in London. I’ve previously lived at two addresses in Sussex and two others in north-east London. While I was growing up, my family lived in a detached house, took holidays to India every year, donated to medical charities, did most of the weekly shopping online at Ocado and read the Financial Times. Now, I rent a recently converted flat owned by a private landlord and have a housemate. I’m interested in movies and startups, have taken five holidays (mostly to visit friends abroad) in the last 12 months and I’m going to buy flights within 14 days. My annual income is probably between £30,000 and £39,999. I don’t have a TV or like watching scheduled television…

The DPA¹¹ provides 8 rights for individuals:

• The right to be informed

• The right of access

• The right to rectification

• The right to erasure

• The right to restrict processing

• The right to data portability

• The right to object

• Rights in relation to automated decision making and profiling.

If we don’t know that data is being collected - or by which organisations - our individual rights are not being protected.

This opens up lots of ethical questions. We’ll discuss these in the next lecture about data ethics.

In this lecture we’re going to focus on the specific risks to deanonymisation

It’s the dangers to individuals that we should primarily be concerned with.

There are significant risks to individual liberty, livelihood and life from deanonymisation.

However, organisations also suffer if data they store/process is deanonymised.

• Organisations might suffer reputational damage

• Organisations might suffer legal difficulties, including fines

First and foremost, there is a risk of:

• Information about someone’s private life ending up in the public domain.

This in and of itself should be of concern, but more specifically

• Individuals might suffer distress, embarrassment, or anxiety due to sensitive information being in the public domain

There is also a significant risk from sensitive information being in the public domain that:

• Individuals might suffer harassment, attack and/or injury

• Individuals might suffer persecution

Sensitive information might be sold to third-party organisations resulting in a change in service options, costs or other loss.

• Private healthcare data might be used by insurers to increase product fees or terminate existing products.

• Employers could potentially use this information in employment decisions.

These are the “protected characteristics” defined in the Equality Act 2010¹³

• Age

• Disability

• Gender reassignment

• Marriage and Civil Partnership

• Pregnancy and Maternity

• Race

• Religion

• Sex

• Sexual Orientation.

Frustratingly, and inhumanely there is prejudice against individuals in all of these groups.

This prejudice can be found in individual actions, from hate groups, as well as institutional policies and practices.

De-anonymisation of health data can realistically [and often easily] expose individual’s protected characteristics.

All individual data should be considered private, but there are significant risks to the de-anonymisation of sensitive healthcare data.

Latanya Sweeney showed in 1997¹⁴ that using public data and the Massachusetts voting list (n=54,805) it was extremely easy to uniquely identify individuals from only 2 pieces of information.

Source: Latanya Sweeney in 1997¹⁴

Three years later in 2000 Latanya Sweeney¹⁵ demonstrated

87% of the US population can be uniquely identified from only ZIP, gender and date of birth.

Source: Latanya Sweeney in 2000¹⁵

Two years later in 2002¹ a statistical technique called k-anonymity was introduced to measure the risk of re-identification.

… by Latanya Sweeney¹⁶!

Originally her research into de-anonymisation was poorly received.

k-anonymity is a property of a dataset that has been subject to anonymisation.

k-anonymity is an integer value that guarantees internal uniqueness of individuals amongst k - 1 individuals.

Unfortunately, a lot of the material written about k-anonymity is confusing because people don’t declare their assumptions in calculating k values.

Let’s consider a simple pretend dataset.

We consider each column in the data to be an attribute.

These attributes can be categorised into two types of identifer:

• Unique identifiers

  • These are attributes that uniquely identify individuals. These have to be removed for anonymisation.

• Quasi-indentifiers

  • These attributes could be used used to identify individuals, even after anonymisation.

Now we’ve thrown away the unique identifiers we need to decide which attributes are sensitive.

Sensitive attributes are medical/healthcare data that we need to protect from in the anonymisation process.

There are now 3 different choices about how we calculate k-anonymity for our data.

• Combining together all non-sensitive attributes compared to each sensitive attributes.

• Combining together all attributes

• For each individual attributes

Let’s go through each of these in turn.

Combining together all non-sensitive attributes compared to each sensitive attributes.

In toy example like this we can go through manually any count how many individuals belong to each group.

Using this measure the dataset is 4-anonymous as all individuals are guaranteed anonymity amongst 3 others (ie k-1).

Combining together all attributes

When we measure across all attributes the k-anonymity of the dataset is reduced.

Using this metric, the data has 3-anonymity.

For each individual attribute

When we measure the anonymity of each individual variable the dataset has 2-anonymity

We always use the smallest value of k for our specific measure.

As we’ve seen, each of these methods gives a different measure of the anonymity of the data.

1. Combining together all non-sensitive attributes compared to each sensitive attributes.

2. Combining together all attributes

3. For each individual attributes

Frustratingly it’s quite rare for authors to explicitly state which combination of attributes they use.

The methods are listed roughly in terms of the frequency that I’ve seen them in the literature.

The definition I’ve given you is sufficient and precise.

But be aware that you’ll often¹⁶ see a more technical definition that uses set theory notation.

Ignore it. If a dataset is described as having “k-anonymity 10” that means for any row in the dataset there are at least 9 other rows identical to it.

When thinking about making this anonymous…

• Are there any variables we should suppress?

• How could we generalise the remaining variables?

• Background knowledge

  • This is the most common attack vector and the Achilles’ heel of k-anonymity.

  • In these attacks background knowledge of relationships between quanti-identifiers is used to reduce anonymity.

  • High dimensionality means lots of quasi-identifiers.

… so where do we go next?

Source: Narayanan and Shmatikov 2008²⁰

l-diversity is a more sophisticated measure of the anonymity of sensitive variables in an anonymised dataset - introduced by Machanavajjhala et al in 2006²¹

This method depends on a Bayesian model of background knowledge.

We are not going to cover Bayesian statistics. Read statswithr.github.io/book/ if you’re interested.

In order to estimate l-diversity we need to once again consider the structure of our dataset.

We split our data into:

• Sensitive variables - the medical variables.

• Keys - the non-sensitive variables.

A dataset is l-diverse if for each unique combination of key attributes there are at least l “well-represented” values for each sensitive variable.

A dataset is l-diverse if for each unique combination of key attributes there are at least l “well-represented” values for each sensitive variable.

For very simple datasets we can calculate l-diversity by hand.

k-anonymity has well known vulnerabilities for high-dimensional datasets.

However. It is still worthwhile establishing at least 5-anonymity²⁰ in released datasets containing sensitive attributes.

Source: Narayanan and Shmatikov 2008[]

Even though a minimum k value of 3 is often suggested, a common recommendation in practice is to ensure that there are at least five similar observations (k = 5)¹⁹

In October 2006 Netflix created a competition with the intention of improving their recommendation engine²².

Netflix sought an algorithm/methodology that would improve their recommendation algorithm.

Let’s get into this a little bit more.

With the announcement of a 2nd competition in 2009 a class-action suit was filed.

The suit described the Netlix Prize dataset as the biggest “voluntary privacy breach to date”. The Federal Trade Commission (FTC) also got involved.

Unfortunately, the case was settled privately so we don’t know the damages. The best I can get is this quote from a deleted blogpost²⁵:

“To some, renting a movie such as Brokeback Mountain or even The Passion of the Christ can be a personal issue that they would not want published to the world.”

Jane Doe, a lesbian, who does not want her sexuality nor interests in gay and lesbian themed films broadcast to the world, seeks anonymity in this action

The exact mechanics of the algorithm behind Arvind Narayanan and Vitaly Shmatikov²⁰ re-identification attack are beyond the scope of this course.

We’re going to walk through the mechanics of the attack.

It’s important to identify this paper introduces a robust statistical de-anonymisation of large sparse datasets that is not unique to the Netflix dataset.

With 8 movie ratings (of which we allow 2 to be completely wrong) and dates that may have a 3-day error, 96% of Netflix subscribers whose records have been released can be uniquely identified in the dataset.

Source: arXiv pre-print 2006²⁴

The de-anonymisation attack is powered by two data sources:

• IMDB Ratings

The authors have written an extremely useful FAQ²⁶.

IMDB provides a large, public database of movie ratings.

An assumed similarity between Netflix and IMDB ratings provides a re-identification attack vector.

The paper provides a proof of concept attack using only 50 IMDB users.

Despite this, the authors are confident of positively cross-matching at least 2 users between the datasets.

The de-anonymisation attack is powered by two data sources:

• IMDB Ratings

The authors have written an extremely useful FAQ²⁶.

Users do not need to have account on both IMDB and Netflix.

Q: Your algorithm only works if the person has accounts on both IMDb and Netflix and rates the same movies on both.

First, our algorithm is not specific to IMDb. You can run our algorithm for any person if they were a Netflix subscriber back in 2005 and you know a little bit about their movie viewing history.

Second, the IMDb record does not have to be the same as the Netflix record. Even a small intersection between the two records is sufficient for our algorithm to succeed with high statistical confidence.

The de-anonymisation attack is powered by two data sources:

• Date of movie review

The authors have written an extremely useful FAQ²⁶.

Date of movie rating provides an additional attack vector.

Background knowledge might include account creation date, providing an attack vector for that user.

Facebook has a long and awful history of privacy breaches and questionable activity.

Facebook Beacon is one of the oldest examples, all the way back from 2007.

It’s a rare example where Mark Zuckerberg open talks about it as a mistake²⁷.

Discuss why Facebook Beacon breaches user privacy

Beacon was designed to automatically post purchases to your friend’s Facebook feeds.

The company originally claimed the service was “opt-in”, but there was clear evidence this was not true.

However, after criticism Facebook provided an opt-out. Users were required to turn off the service.

A class action suit in 2009 was settled for $9.5million.

Do you know what these machines are for in Tesco?

These devices have embedded cameras that can track customer gaze - a proxy for the their attention.

The video feed from these devices is processed by software by Quividi that can estimate³¹:

• Gender

• Age

• Mood

Their privacy page makes for interesting reading.

“Quividi’s software employs advanced facial detection software, not facial recognition technologies.” Quividi marketing

In 2021 Zuo et al³² performed a systematic review of de-anonymisation tools in digital health care.

There were two off-the-shelf tools identified that were built with R

• {sdcMicro}

  • This package contains many tools for measuring/exploring the anonymity of datasets via a {shiny} app.

• `{ShinyAnonymizer}

  • This package provides a {shiny} app for anonymising healthcare data

However. There isn’t a one-size fits all methodology or guarantee of privacy through anonymisation.

k-anonymity and l-diversity are useful metrics and provide some assurance of privacy. But background knowledge attacks might undermine these.

We need to be vigilant and careful when:

• Preparing data for release

• Designing services

We’ve used the {wakefield} package to create fake datasets.

The {faux} package is a more sophisticated package for simulating datasets designed by Lise DeBruine.

This is an excellent module on privacy from Carnegie Mellon University.

You can find all lecture materials and even exercises here: https://course.ece.cmu.edu/~ece734/fall2019/syllabus.html

This quickly becomes very technical.

Ashwin Machanavajjhala has an excellent course about privacy in a mobile world - https://courses.cs.duke.edu/fall13/compsci590.3/

This quickly becomes very technical.